/**
 * 865. 具有所有最深节点的最小子树
 * https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/
 */
public class Solutions_865 {
    public static void main(String[] args) {
//        String str = "[3 5 1 6 2 0 8 # # 7 4]";  // output: 2
//        String str = "[1]";  // output: 1
        String str = "[0 1 3 # 2]";  // output: 2

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        TreeNode result = subtreeWithAllDeepest(root);
        System.out.println(MyTreeNodeUtils.serialize(result));
    }

    /**
     * 1. 获取左、右子树的深度
     * 2. 左、右子树深度相同，则以当前节点为根的子树中包含所有最深的节点
     * 3. 左、右子树深度不同，递归进入深度较大的一侧
     */
    public static TreeNode subtreeWithAllDeepest(TreeNode root) {
        if (root == null) {
            return root;
        }
        // 获取左、右子树的深度
        int leftDeep = MyTreeNodeUtils.getDeep(root.left);
        int rightDeep = MyTreeNodeUtils.getDeep(root.right);
        // 左、右子树深度相同，则以当前节点为根的子树中包含所有最深的节点
        if (leftDeep == rightDeep) {
            return root;
        }
        // 左、右子树深度不同，递归进入深度较大的一侧
        TreeNode node = leftDeep > rightDeep ? root.left : root.right;
        return subtreeWithAllDeepest(node);
    }
}
